Internet Traffic consists of ordered sequences of packets, or datagrams, where each packet contains header and data. The data contained in each packet usually holds only a fraction from a larger set of data which has been chopped up into pieces and portioned into packets at the source to be gathered and assembled into the original data when reaching the destination.
In the packet header, addressing and protocol information are stored in a number of header fields. For some of these header fields the value changes with each packet while other fields are constant throughout the existence of a communication session. Packets with identical values of the constant fields are typically considered to belong to the same traffic flow.
For security reasons it is sometimes desirable to block certain traffic. This is accomplished by using a firewall. A Firewall is a security device with the main purpose of inspecting traffic and decide whether it is allowed through the firewall or not according to a security policy. The security policy is often entered manually by a system administrator and defines a mapping from potential traffic flows to actions that describes how to process the traffic. To qualify as a firewall, at least two different kinds of actions must be supported: drop and forward. Many commercial firewalls also serve as routers and many commercial routers have at least some firewall functionality. In the following discussion we will use the term router to mean both routers, firewalls as well as combinations of the two.
Packet classification is sometimes referred to as multiple field classification (MFC). The problem is similar to forwarding decisions as header fields match intervals (an address prefix can be represented by an interval) in the most general sense. Multiple fields are matched simultaneously making MFC a D-dimensional classification problem as opposed to forwarding decisions which is a 1-dimensional classification problem.